#include <iostream>
#include <vector>

using namespace std;

class Solution
{
public:
    int maxProfit(vector<int> &prices, int fee)
    {
        // buy[i,0],sell[i,1]
        int buy = -prices[0] - fee;
        int sell = 0;
        for (int i = 1; i < prices.size(); i++)
        {
            int newbuy = max(buy, sell - prices[i] - fee);
            int newsell = max(sell, buy + prices[i]);
            buy = newbuy;
            sell = newsell;
        }
        return sell;
    }
};

int main()
{
    cout << "Code714" << endl;
    Solution s;
    vector<int> prices1 = {1, 3, 2, 8, 4, 9};
    vector<int> prices2 = {1, 3, 7, 5, 10, 3};
    vector<int> prices3 = {9, 8, 7, 1, 2};
    cout << s.maxProfit(prices1, 2) << endl;
    cout << s.maxProfit(prices2, 3) << endl;
    cout << s.maxProfit(prices3, 3) << endl;
    return 0;
}